<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,100分)- 机器人搬砖（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>机器人搬砖&#xff0c;一共有 N 堆砖存放在 N 个不同的仓库中&#xff0c;第 i 堆砖中有 bricks[i] 块砖头&#xff0c;要求在 8 小时内搬完。</p> 
<p>机器人每小时能搬砖的数量取决于有多少能量格&#xff0c;机器人一个小时中只能在一个仓库中搬砖&#xff0c;机器人的能量格只在这一个小时有效&#xff0c;为使得机器人损耗最小化&#xff0c;应尽量减小每次补充的能量格数。</p> 
<p>为了保障在 8 小时内能完成搬砖任务&#xff0c;请计算每小时给机器人充能的最小能量格数。</p> 
<ul><li>无需考虑机器人补充能力格的耗时&#xff1b;</li><li>无需考虑机器人搬砖的耗时&#xff1b;</li><li>机器人每小时补充能量格只在这一个小时中有效&#xff1b;</li></ul> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第一行为一行数字&#xff0c;空格分隔</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>机器人每小时最少需要充的能量格&#xff0c;若无法完成任务&#xff0c;输出 -1</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">30 12 25 8 19</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">15</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">10 12 25 8 19 8 6 4 17 19 20 30</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">-1</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">砖的堆数为12堆存放在12个仓库中&#xff0c;机器人一个小时内只能在一个仓库搬砖&#xff0c;不可能完成任务。</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题有个关键说明&#xff1a;</p> 
<blockquote> 
 <p>机器人一个小时中只能在一个仓库中搬砖</p> 
</blockquote> 
<p>另外&#xff1a;</p> 
<blockquote> 
 <p>机器人搬砖&#xff0c;一共有 N 堆砖存放在 N 个不同的仓库中&#xff0c;第 i 堆砖中有 bricks[i] 块砖头&#xff0c;<span style="color:#fe2c24;">要求在 8 小时内搬完</span></p> 
</blockquote> 
<p></p> 
<p>机器人一个小时只能在一个仓库干活&#xff0c;那么在8小时内&#xff0c;机器人最多干完8个仓库。</p> 
<ul><li>如果bricks.length &gt; 8&#xff0c;那么机器人肯定不可能在8小时内干完。</li><li>如果bricks.length &lt;&#61; 8&#xff0c;此时我们可以通过二分法求解最少每小时充电量&#xff1b;<br /><br /> 假设机器人每个小时需要 k 格能量</li></ul> 
<ol><li>如果只有一个仓库一堆砖&#xff0c;那么这堆砖就可以平分到8小时内搬&#xff0c;这样才能保证每小时搬最少的砖&#xff0c;消耗最少的能量&#xff0c;即每小时可以充最少的能量。如果这堆砖头足够少&#xff0c;比如只有1块&#xff0c;那么此时机器人每小时只需要充1块能量即可。因此 k 的最小值取 1。</li><li>如果有8个仓库&#xff0c;那么机器人每小时的能量格数至少就是 max(bricks)&#xff0c;这样才能保证一个小时干完砖头数量最多的那个仓库。因此 k 的最大值取max(bricks)。</li></ol> 
<p>求出 k 的取值范围后&#xff0c;我们可以通过二分取中值的方式&#xff0c;不停尝试可能解mid&#xff1a;</p> 
<ul><li>如果mid能量块可以满足8小时内搬完所有仓库&#xff0c;那么mid就是一个可能解&#xff0c;但不一定是最优解&#xff0c;此时我们应该尝试充更少的能量&#xff0c;即缩小k的右边界范围到 &#61; mid - 1</li><li>如果mid能量块不能满足8小时内搬完所有仓库&#xff0c;那么说明每小时充mid能力太少了&#xff0c;我们应该尝试充更多能量&#xff0c;即增大k的左边界范围到 &#61; mid &#43; 1</li></ul> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

void (async function () {
  const bricks &#61; (await readline()).split(&#34; &#34;).map(Number);
  console.log(getResult(bricks));
})();

function getResult(bricks) {
  // 机器人每小时只能在一个仓库干活&#xff0c;因此给定8小时&#xff0c;最多只能搬完8个仓库&#xff0c;如果仓库数量超过8&#xff0c;那么肯定干不完
  if (bricks.length &gt; 8) {
    return -1;
  }

  // 每小时最多需要的能量块
  let max &#61; Math.max(...bricks);

  // 如果有8个仓库&#xff0c;那么只能1个小时干1个仓库&#xff0c;且机器人每小时需要能量至少是max(bricks)&#xff0c;这样才能保证1个小时内把最多砖块的那个仓库搬完
  if (bricks.length &#61;&#61; 8) {
    return max;
  }

  // 如果仓库数少于8个&#xff0c;那么此时每小时能量max(bricks)必然能在8小时内搬完所有仓库&#xff0c;但不是最优解
  let ans &#61; max;

  // 每小时最少需要的能量块
  let min &#61; 1;

  // 二分法
  while (min &lt;&#61; max) {
    // 取中间值
    const mid &#61; (min &#43; max) &gt;&gt; 1;

    if (check(mid, 8, bricks)) {
      // 如果每小时充mid格能量&#xff0c;就能在8小时内&#xff0c;搬完所有砖头&#xff0c;则mid就是一个可能解
      ans &#61; mid;
      // 但mid不一定是最优解&#xff0c;因此继续尝试更小的能量块
      max &#61; mid - 1;
    } else {
      // 如果每小时充mid能量块&#xff0c;无法在8小时能完成工作&#xff0c;则说明每天能量块充少了&#xff0c;下次应该尝试充更多能量块
      min &#61; mid &#43; 1;
    }
  }

  return ans;
}

/**
 *
 * &#64;param {*} energy 每小时可以使用的能量块数量
 * &#64;param {*} limit 限制几小时内干完
 * &#64;param {*} bricks 要搬的几堆砖头
 * &#64;returns 是否可以在limit小时内已指定energy能量搬完所有bricks
 */
function check(energy, limit, bricks) {
  // 已花费的小时数
  let cost &#61; 0;

  for (let brick of bricks) {
    cost &#43;&#61; Math.ceil(brick / energy);

    // 如果搬砖过程中发现&#xff0c;花费时间已经超过限制&#xff0c;则直接返回false
    if (cost &gt; limit) {
      return false;
    }
  }

  return true;
}
</code></pre> 
<p></p> 
<h4 id="Java%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">Java算法源码</h4> 
<pre><code class="language-java">import java.util.Arrays;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);
    int[] bricks &#61; Arrays.stream(sc.nextLine().split(&#34; &#34;)).mapToInt(Integer::parseInt).toArray();
    System.out.println(getResult(bricks));
  }

  public static int getResult(int[] bricks) {
    // 机器人每小时只能在一个仓库干活&#xff0c;因此给定8小时&#xff0c;最多只能搬完8个仓库&#xff0c;如果仓库数量超过8&#xff0c;那么肯定干不完
    if (bricks.length &gt; 8) {
      return -1;
    }

    // 每小时最多需要的能量块
    int max &#61; Arrays.stream(bricks).max().orElse(0);

    // 如果有8个仓库&#xff0c;那么只能1个小时干1个仓库&#xff0c;且机器人每小时需要能量至少是max(bricks)&#xff0c;这样才能保证1个小时内把最多砖块的那个仓库搬完
    if (bricks.length &#61;&#61; 8) {
      return max;
    }

    // 如果仓库数少于8个&#xff0c;那么此时每小时能量max(bricks)必然能在8小时内搬完所有仓库&#xff0c;但不是最优解
    int ans &#61; max;

    // 每小时最少需要的能量块
    int min &#61; 1;

    // 二分法
    while (min &lt;&#61; max) {
      // 取中间值
      int mid &#61; (min &#43; max) &gt;&gt; 1;

      if (check(mid, 8, bricks)) {
        // 如果每小时充mid格能量&#xff0c;就能在8小时内&#xff0c;搬完所有砖头&#xff0c;则mid就是一个可能解
        ans &#61; mid;
        // 但mid不一定是最优解&#xff0c;因此继续尝试更小的能量块
        max &#61; mid - 1;
      } else {
        // 如果每小时充mid能量块&#xff0c;无法在8小时能完成工作&#xff0c;则说明每天能量块充少了&#xff0c;下次应该尝试充更多能量块
        min &#61; mid &#43; 1;
      }
    }

    return ans;
  }

  /**
   * &#64;param energy 每小时可以使用的能量块数量
   * &#64;param limit 限制几小时内干完
   * &#64;param bricks 要搬几堆砖头
   * &#64;return 是否可以在limit小时内已指定energy能量办完所有bricks
   */
  public static boolean check(int energy, int limit, int[] bricks) {
    // 已花费的小时数
    int cost &#61; 0;

    for (int brick : bricks) {
      cost &#43;&#61; brick / energy &#43; (brick % energy &gt; 0 ? 1 : 0);

      // 如果搬砖过程中发现&#xff0c;花费时间已经超过限制&#xff0c;则直接返回false
      if (cost &gt; limit) {
        return false;
      }
    }

    return true;
  }
}
</code></pre> 
<p></p> 
<h4 id="Python%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">Python算法源码</h4> 
<pre><code class="language-python">import math

# 输入获取
bricks &#61; list(map(int, input().split()))


def check(energy, limit):
    &#34;&#34;&#34;
    :param energy: 每小时可以使用的能量块数量&#xff08;搬一块砖消耗一块能量&#xff09;
    :param limit: 限制几小时内干完
    :return: 是否可以在limit小时内搬完所有bricks
    &#34;&#34;&#34;
    cost &#61; 0  # 已花费的小时数

    for brick in bricks:
        cost &#43;&#61; math.ceil(brick / energy)

        # 如果搬砖过程中发现&#xff0c;花费时间已经超过限制&#xff0c;则直接返回false
        if cost &gt; limit:
            return False

    return True


# 算法入口
def getResult():
    # 机器人每小时只能在一个仓库干活&#xff0c;因此给定8小时&#xff0c;最多只能搬完8个仓库&#xff0c;如果仓库数量超过8&#xff0c;那么肯定干不完
    if len(bricks) &gt; 8:
        return -1

    # 每小时最多需要的能量块
    maxEnergy &#61; max(bricks)

    # 如果有8个仓库&#xff0c;那么只能1个小时干1个仓库&#xff0c;且机器人每小时需要能量至少是max(bricks)&#xff0c;这样才能保证1个小时内把最多砖块的那个仓库搬完
    if len(bricks) &#61;&#61; 8:
        return maxEnergy

    # 如果仓库数少于8个&#xff0c;那么此时每小时能量max(bricks)必然能在8小时内搬完所有仓库&#xff0c;但不是最优解
    ans &#61; maxEnergy

    # 每小时最少需要的能量块
    minEnergy &#61; 1

    # 二分法
    while minEnergy &lt;&#61; maxEnergy:
        # 取中间值
        mid &#61; (minEnergy &#43; maxEnergy) &gt;&gt; 1

        if check(mid, 8):
            # 如果每小时充mid格能量&#xff0c;就能在8小时内&#xff0c;搬完所有砖头&#xff0c;则mid就是一个可能解
            ans &#61; mid
            # 但mid不一定是最优解&#xff0c;因此继续尝试更小的能量块
            maxEnergy &#61; mid - 1
        else:
            # 如果每小时充mid能量块&#xff0c;无法在8小时能完成工作&#xff0c;则说明每天能量块充少了&#xff0c;下次应该尝试充更多能量块
            minEnergy &#61; mid &#43; 1

    return ans


# 算法调用
print(getResult())
</code></pre> 
<p></p> 
<h4 id="C%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;limits.h&gt;

#define MAX(a, b) ((a) &gt; (b) ? (a) : (b))

#define MAX_SIZE 100000

/*!
 *
 * &#64;param energy 每小时可以使用的能量块数量
 * &#64;param limit 限制几小时内干完
 * &#64;param bricks 要搬走的砖
 * &#64;param bricks_size 砖的堆数
 * &#64;return 是否可以在limit小时内搬完所有bricks
 */
int check(int energy, int limit, const int bricks[], int bricks_size) {
    // 已花费的天数
    int cost &#61; 0;

    for (int i &#61; 0; i &lt; bricks_size; i&#43;&#43;) {
        cost &#43;&#61; bricks[i] / energy &#43; (bricks[i] % energy &gt; 0 ? 1 : 0);

        // 如果搬砖过程中发现&#xff0c;花费时间已经超过限制&#xff0c;则直接返回false
        if (cost &gt; limit) {
            return 0;
        }
    }

    return 1;
}

int getResult(const int bricks[], int bricks_size) {
    // 机器人每小时只能在一个仓库干活&#xff0c;因此给定8小时&#xff0c;最多只能搬完8个仓库&#xff0c;如果仓库数量超过8&#xff0c;那么肯定干不完
    if (bricks_size &gt; 8) {
        return -1;
    }

    // 每小时最多需要的能量块
    int max &#61; INT_MIN;
    for (int i &#61; 0; i &lt; bricks_size; i&#43;&#43;) {
        max &#61; MAX(max, bricks[i]);
    }

    // 如果有8个仓库&#xff0c;那么只能1个小时干1个仓库&#xff0c;且机器人每小时需要能量至少是max(bricks)&#xff0c;这样才能保证1个小时内把最多砖块的那个仓库搬完
    if(bricks_size &#61;&#61; 8) {
        return max;
    }

    // 如果仓库数少于8个&#xff0c;那么此时每小时能量max(bricks)必然能在8小时内搬完所有仓库&#xff0c;但不是最优解
    int ans &#61; max;

    // 每小时最少需要的能量块
    int min &#61; 1;

    // 二分法
    while (min &lt;&#61; max) {
        // 取中间值
        int mid &#61; (min &#43; max) &gt;&gt; 1;

        if (check(mid, 8, bricks, bricks_size)) {
            // 如果每小时充mid格能量&#xff0c;就能在8小时内&#xff0c;搬完所有砖头&#xff0c;则mid就是一个可能解
            ans &#61; mid;
            // 但mid不一定是最优解&#xff0c;因此继续尝试更小的能量块
            max &#61; mid - 1;
        } else {
            // 如果每小时充mid能量块&#xff0c;无法在8小时能完成工作&#xff0c;则说明每天能量块充少了&#xff0c;下次应该尝试充更多能量块
            min &#61; mid &#43; 1;
        }
    }

    return ans;
}

int main() {
    int bricks[MAX_SIZE];
    int bricks_size &#61; 0;

    while (scanf(&#34;%d&#34;, &amp;bricks[bricks_size&#43;&#43;])) {
        if (getchar() !&#61; &#39; &#39;) break;
    }

    printf(&#34;%d\n&#34;, getResult(bricks, bricks_size));

    return 0;
}</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>